package com.austin.framework.test;

import java.util.Arrays;

/**
 * 排序算法
 *
 * @author: austin
 * @since: 2023/2/22 22:30
 */
public class SortAlgorithmExample {

    /**
     * 冒泡排序算法
     */
    public static int[] bubbleSort(int[] array) {
        if (array == null || array.length == 0) {
            return array;
        }
        int temp = 0;
        // i < array.length, eg: array的长度为5，只需要对比4次，0,1,2,3
        for (int i = 0; i < array.length - 1; i++) {
            // j<4 j<3 j<2 j<1
            for (int j = 0; j < array.length - 1 - i; j++) {
                // 如果前面的数大于后面的数，交换
                if (array[j] > array[j + 1]) {
                    temp = array[j];            //将大的赋值给temp
                    array[j] = array[j + 1];    //将小的赋值给前面的值array[j]
                    array[j + 1] = temp;        //将暂存大值的temp赋值给后面的值array[j+1]
                }
            }
        }
        return array;
    }

    /**
     * 直接插入排序算法
     */
    public static int[] insertSort(int[] array) {
        if (array == null || array.length == 0) {
            return array;
        }
        // 第0位独自作为有序数列，从第1位开始向后遍历
        for (int i = 1; i < array.length; i++) {
            //0~i-1位为有序，若第i位小于i-1位，继续寻位并插入，否则认为0~i位也是有序的，忽略此次循环，相当于continue
            if (array[i] < array[i - 1]) {
                int temp = array[i];    //保存第i位的值
                int j = i - 1;
                //从第i-1位向前遍历并移位，直至找到小于第i位值停止
                while (j >= 0 && temp < array[j]) {
                    array[j + 1] = array[j];
                    j--;
                }
                array[j + 1] = temp;//插入第i位的值
            }
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = {1, 5, 2, 6, 3, 8, 11};
        System.out.println(Arrays.toString(bubbleSort(array)));
        System.out.println(Arrays.toString(insertSort(array)));
    }
}
